package com.wrial.middle;
/*
 * @Author  Wrial
 * @Date Created in 21:20 2020/8/1
 * @Description
 *
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]
 */

import java.util.ArrayList;
import java.util.List;

public class LeetCode_22_括号生成 {

    /**
     * 1.暴力递归法（生成全部序列，然后挨个进行校验） 时间复杂度O(2的2n次方*n)n是校验需要的时间复杂度
     * 2.
     *
     * @param n
     * @return
     */
//    public List<String> generateParenthesis(int n) {
//        if (n <= 0) return null;
//        List<String> ans = new ArrayList<>();
//        generate(new char[2 * n], 0, ans);
//        return ans;
//    }
//
//    private void generate(char[] arr, int currentPos, List<String> ans) {
//        if (currentPos == arr.length) {
//            if (valid(arr)) {
//                ans.add(new String(arr));
//            }
//        } else {
//            // 如果没有生成够2n个符号，那就继续生成（不是左括号就是右括号）
//            arr[currentPos] = '(';
//            generate(arr,currentPos+1,ans);
//            arr[currentPos] = ')';
//            generate(arr, currentPos + 1, ans);
//        }
//    }
//
//    private boolean valid(char[] arr) {
//
//        int count = 0;
//        for (char c : arr) {
//            if (c == '(') count++;
//            else count--;
//            if (count<0) return false;
//        }
//        return count == 0 ? true : false;
//    }

    //2.dfs
    public List<String> generateParenthesis(int n) {
        if (n <= 0) return null;
        List<String> ans = new ArrayList<>();
        generate(ans, "", n, n);
        return ans;
    }

    private void generate(List<String> ans, String currentStr, int left, int right) {

        if (left == 0 && right == 0) {
            ans.add(currentStr);
            return;
        }
        // 剩下的left多说明append的left少，说明不合法
        if (left > right) {
            return;
        }

        if (left > 0) {
            generate(ans, "(" + currentStr, left - 1, right);
        }
        if (right > left) {
            generate(ans, ")" + currentStr, left, right - 1);
        }
    }

}
